/**
 * 剑指 Offer 12. 矩阵中的路径
 * https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/
 */

/**
 * @param {string} word
 * @param {number} begin
 * @param {string[][]} board
 * @param {number} i
 * @param {number} j
 * @param {number[][]} sign
 * @param {number} curSign
 */
function search(word, begin, board, i, j, sign, curSign) {
  if (begin >= word.length) {
    return true;
  }
  if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) {
    return false;
  }
  const oldSign = sign[i][j];
  if (board[i][j] !== word[begin] || oldSign === curSign) {
    return false;
  }
  sign[i][j] = curSign;
  if (
    search(word, begin + 1, board, i + 1, j, sign, curSign)
    || search(word, begin + 1, board, i, j + 1, sign, curSign)
    || search(word, begin + 1, board, i - 1, j, sign, curSign)
    || search(word, begin + 1, board, i, j - 1, sign, curSign)
  ) {
    return true;
  }
  sign[i][j] = oldSign;
  return false;
}

/**
 * @param {string[][]} board
 * @param {string} word
 * @return {boolean}
 */
function exist(board, word) {
  const { length: n } = board;
  const { length: m } = board[0];
  const sign = new Array(n);
  for (let i = 0; i < n; i += 1) {
    sign[i] = new Array(m).fill(-1);
  }
  let curSign = 0;
  for (let i = 0; i < n; i += 1) {
    for (let j = 0; j < m; j += 1, curSign += 1) {
      if (search(word, 0, board, i, j, sign, curSign)) {
        return true;
      }
    }
  }
  return false;
}

console.log(exist([
  ['A', 'B', 'C', 'E'],
  ['S', 'F', 'C', 'S'],
  ['A', 'D', 'E', 'E'],
], 'ABCCED') === true);
console.log(exist([
  ['a', 'b'],
  ['c', 'd'],
], 'abcd') === false);
